package com.acwing.partition9;

import java.io.*;

/**
 * @author `RKC`
 * @date 2021/12/9 14:33
 */
public class AC890能被整除的数 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        s = reader.readLine().split(" ");
        int[] primes = new int[m];
        for (int i = 0; i < m; i++) primes[i] = Integer.parseInt(s[i]);
        writer.write(String.valueOf(inclusionExclusion(n, primes)));
        writer.flush();
    }

    /**
     * 如n=10，primes={2, 3}
     * S1={2, 4, 6, 8. 10}, S2={3, 6, 9}，那么S1∩S2={6}
     * |S1∪S2|=|S1|+|S2|-|S1∩S2|=5+3-1=7
     * 时间复杂度O(2^m)
     */
    private static int inclusionExclusion(int n, int[] primes) {
        int m = primes.length, answer = 0;
        //状态压缩来表示对应的集合是否被选中
        for (int status = 1; status < 1 << m; status++) {
            //当前状态选中的集合对应的质数的乘积和选出的集合的数量
            int mul = 1, count = 0;
            for (int i = 0; i < m; i++) {
                if ((status >> i & 1) == 1) {
                    if ((long) mul * primes[i] > n) {
                        mul = -1;
                        break;
                    }
                    mul *= primes[i];
                    count++;
                }
            }
            if (mul == -1) continue;
            //奇数个数集合被选中就加，偶数个数集合就相减
            answer = (count & 1) == 1 ? answer + n / mul : answer - n / mul;
        }
        return answer;
    }
}
